package dp

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/
// 计算买卖股票的最大利润
// 算法: 动态规划
// 时间复杂度: O(n)
// 公式: 卖或者不卖 两种选择 ，minprice[n] = min(prices[n], minprice[n-1]), f[n] = max(f[n] - minprice[n-1], f[n-1])
// func maxInt(a, b int) int {
// 	if a > b {
// 		return a
// 	} else {
// 		return b
// 	}
// }

// func minInt(a, b int) int {
// 	if a < b {
// 		return a
// 	} else {
// 		return b
// 	}
// }

func MaxProfit(prices []int) int {
	if 0 == len(prices) {
		return 0
	}

	minPriceArr := make([]int, len(prices))
	maxProfitArr := make([]int, len(prices))
	minPriceArr[0] = prices[0]
	maxProfitArr[0] = 0

	for index := 1; index < len(prices); index++ {
		minPriceArr[index] = minInt(prices[index], minPriceArr[index-1])
		maxProfitArr[index] = maxInt(prices[index]-minPriceArr[index-1], maxProfitArr[index-1])
	}

	return maxProfitArr[len(prices)-1]
}
